package cn.leonis.leetcode;

/**
 * @author Tobi
 * @time 2021-07-10 11:04 AM
 * 查找插入位置，也是二分查找的应用
 * 题目：给出一个有序的数组和待插入的值，查询该值插入的位置
 * leetcode35
 */
public class SearchInsertPositionSolution {

    public static void main(String[] args) {
        int[]  nums = new int[]{1, 3, 5, 6};
        int target = 0;
        SearchInsertPositionSolution solution = new SearchInsertPositionSolution();
        System.out.println(solution.searchInsert(nums, target));
    }

    public int searchInsert(int[] nums, int target) {
        int length = nums.length;
        int pl = 0, pr = length - 1, answer = length;
        while (pl <= pr) {
            int mid = pl + ((pr - pl) >> 1);
            if (target <= nums[mid]) {
                answer = mid;
                pr = mid - 1;
            }else {
                pl = mid + 1;
            }
        }

        return answer;
    }
}
